package bm9;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 23:43
 * BM9.删除链表中倒数第 n 个节点
 * https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tqId=1377477&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 哑巴节点, 便于处理删除头指针的情况, 最终返回结果是 muteNode.next
        ListNode muteNode = new ListNode(-1);
        muteNode.next = head;
        // 要想删除倒数第 n 个节点, 则需要找到倒数第 n + 1 个节点
        ListNode fast = muteNode;
        ListNode slow = muteNode;
        n = n + 1;
        while (n-- > 0) {
            if (fast == null) {
                return head; // 说明 n 不合法, 不进行处理
            }
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 此时 slow 指向倒数第 n 个节点的前驱
        slow.next = slow.next.next; // 删除
       return muteNode.next;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
